I. Field of the Invention
The present invention relates to the Shannon bound on communications capacity and also relates to symbol modulation and demodulation and convolutional and turbo encoding and decoding for high-data-rate wired, wireless, and optical communications and includes the symbol modulations phase-shift-keying PSK, quadrature amplitude modulation QAM, bandwidth efficient modulation BEM, gaussian minimum shift keying GMSK, pulse position modulation PPM, and the plurality of current and future modulations for single links and multiple access links which include time division multiple access TDMA, frequency division multiple access FDMA, code division multiple access CDMA, spatial division multiple access SDMA, frequency hopping FH, optical wavelength division multiple access WDMA, orthogonal Wavelet division multiple access OWDMA, combinations thereof, and the plurality of radar, optical, laser, spatial, temporal, sound, imaging, and media applications. Communication application examples include electrical and optical wired, mobile, point-to-point, point-to-multipoint, multipoint-to-multipoint, cellular, multiple-input multiple-output MIMO, and satellite communication networks.
II. Description of the Related Art
The Shannon bound is the Shannon capacity theorem for the maximum data rate C and equivalently can be restated as a bound on the corresponding number of modulation bits per symbol as well as a bound on the communications efficiency and is complemented by the Shannon coding theorem. From Shannon's paper “A Mathematical Theory of Communications” Bell System Technical Journal, 27:379-423, 623-656, October 1948 and B. Vucetic and J. Yuan's book “Turbo Codes”, Kluwer Academic Publishers 2000, the Shannon (Shannon-Hartley theorem) capacity theorem, the corresponding Shannon bound on the information bits b per symbol, the Shannon bound on the communications efficiency η, and the Shannon coding theorem can be written as equations (1).
Shannon bounds and coding theorem(1)1Shannon capacity theoremC                                              ⁢                  =                    ⁢                      B            ⁢                                                  ⁢                          log              2                        ⁢                                                  ⁢                          (                              1                +                                  S                  /                  N                                            )                                                                        =                    ⁢                      Channel            ⁢                                                  ⁢            capacity            ⁢                                                  ⁢            in            ⁢                                                  ⁢            bits            ⁢                          /                        ⁢            second            ⁢                          =                        ⁢            Bps                          ⁢                                  ⁢                                  ⁢                  for          ⁢                                          ⁢          an          ⁢                                          ⁢          additive          ⁢                                          ⁢          white          ⁢                                          ⁢          Gaussian          ⁢                                          ⁢          noise          ⁢                                          ⁢          AWGN                ⁢                                  ⁢                                  ⁢                  channel          ⁢                                          ⁢          with          ⁢                                          ⁢          bandwidth          ⁢                                          ⁢          B          ⁢                                          ⁢                                    wherein              ⁢                                                                    ``                    ⁢                                    log              2                        ″                          ⁢                                  ⁢                                  ⁢                  is          ⁢                                          ⁢          the          ⁢                                          ⁢          logarithm          ⁢                                          ⁢          to          ⁢                                          ⁢          the          ⁢                                          ⁢          base          ⁢                                          ⁢          2                                                  =                    ⁢                      Maximum            ⁢                                                  ⁢            rate            ⁢                                                  ⁢            at            ⁢                                                  ⁢            which            ⁢                                                  ⁢            information            ⁢                                                  ⁢            can            ⁢                                                  ⁢            be                          ⁢                                  ⁢                                  ⁢                  reliably          ⁢                                          ⁢          transmitted          ⁢                                          ⁢          over          ⁢                                          ⁢          a          ⁢                                          ⁢          noisy          ⁢                                          ⁢          channel                ⁢                                  ⁢                                  ⁢                  where          ⁢                                          ⁢                      S            /            N                    ⁢                                          ⁢          is          ⁢                                          ⁢          the          ⁢                                          ⁢          signal          ⁢                      -                    ⁢          to          ⁢                      -                    ⁢          noise          ⁢                                          ⁢          ratio          ⁢                                          ⁢          in          ⁢                                          ⁢          B                     2Shannon bound on b, η, and Eb/No                              max          ⁢                                          ⁢                      {            b            }                          =                ⁢                  max          ⁢                                          ⁢                      {                          C              /              B                        )                                                                            ⁢                  =                    ⁢                                    log              2                        ⁢                                                  ⁢                          (                              1                +                                  S                  /                  N                                            )                                                              =                ⁢                  max          ⁢                                          ⁢                      (            η            )                                                                        E            b                    /                      N            o                          =                ⁢                                            [                                                                    2                    ⋀                                    ⁢                  max                  ⁢                                      {                    b                    }                                                  -                1                            ]                        /            max                    ⁢                                          ⁢                      {            b            }                                 wherein  ⁢          ⁢                                          b            =                          C              ⁢                              /                            ⁢              B                                ,                      Bps            ⁢                          /                        ⁢            Hz            ⁢                          =                        ⁢            Bits            ⁢                          /                        ⁢            symbol                                                                    η            =                          b              ⁢                              /                            ⁢                              T                s                            ⁢              B                                ,                      Bps            ⁢                          /                        ⁢            Hz                                                                    T            s                    =                      symbol            ⁢                                                  ⁢            interval                               3.Shannon coding theorem for the information bit rate RbFor Rb<C there exists codes which support reliablecommunicationsFor Rb>C there are no codes which support reliablecommunications
Using the assumption that the symbol rate 1/Ts is maximized which means 1/Ts=Nyquist rate=bandwidth B and is equivalent TsB=1, enables 1 in equations (1) defining C to be rewritten to calculate max{b} as a function of the signal-to-noise ratio S/N, and to calculate Eb/No which is the ratio of energy per information bit Eb to the noise power density No, as a function of the max{b} in 2 and wherein max{b} is the maximum value of the number of information bits per symbol b. Since the communications efficiency η=b/(TsB) in bits/sec/Hz it follows that maximum values of b and are equal. The derivation of the equation for Eb/No uses the definition Eb/No=(S/N)/b in addition to 1 and 2. Reliable communications in the statement of the Shannon coding theorem 3 means an arbitrarily low bit error rate BER.
Turbo decoding is introduced in equations (2) along with the current MAP (maximum a-posteriori probability) joint probability p(s′,s,y) used for MAP turbo decoding {1},{2}, and the a-posteriori probability of s,s′ given the observations y expressed as the MAP probability p(s,s′|y) and used in a new formulation for MAP turbo decoding in U.S. Pat. No. 7,337,383 B1. We find
MAP joint probability for turbo decoding(2)1 Definitions                               S          ⁢                                          ⁢                      (            k            )                          ⁢                                  =                ⁢                  Decoder          ⁢                                          ⁢          trellis          ⁢                                          ⁢          state          ⁢                                          ⁢          at          ⁢                                          ⁢          clock          ⁢                                          ⁢          k                                                                  ⁢                  =                    ⁢                      Decoder            ⁢                                                  ⁢            shift            ⁢                                                  ⁢            register            ⁢                                                  ⁢            state            ⁢                                                  ⁢            at            ⁢                                                  ⁢            clock            ⁢                                                  ⁢            k                                                  k        ⁢                                  =                ⁢                  Index          ⁢                                          ⁢          of          ⁢                                          ⁢          received          ⁢                                          ⁢          codewords                                                                  ⁢                  =                    ⁢                      trellis            ⁢                                                  ⁢            decoder            ⁢                                                  ⁢            states                                                                            ⁢                  =                    ⁢                      decoding            ⁢                                                  ⁢            clock                                                            s          ′                ,                  s          ⁢                                          =                    ⁢                      Values            ⁢                                                  ⁢            of            ⁢                                                  ⁢                          S              ⁡                              (                                  k                  ⁢                                      -                                    ⁢                  1                                )                                                    ,                              S            ⁡                          (              k              )                                ⁢                                          ⁢          respectively                                        y        ⁢                                  =                ⁢                  Set          ⁢                                          ⁢          of          ⁢                                          ⁢          observed          ⁢                                          ⁢          channel          ⁢                                          ⁢          output          ⁢                                          ⁢          symbols                                                                  ⁢                  =                    ⁢                      {                                          y                ⁡                                  (                  k                  )                                            ,                              k                ⁢                                  =                                ⁢                1                            ,              2              ,              …              ⁢                                                          ,              N                        }                                                  RSC        =                ⁢                  Recursive          ⁢                                          ⁢          systematic          ⁢                                          ⁢          code                                                                  ⁢                  =                    ⁢                      Systematic            ⁢                                                  ⁢            code            ⁢                                                  ⁢            SC            ⁢                                                  ⁢            with            ⁢                                                  ⁢            feedback            ⁢                                                  ⁢            which            ⁢                                                  ⁢            is            ⁢                                                  ⁢            a                                                                           ⁢                  requirement          ⁢                                          ⁢          for          ⁢                                          ⁢          turbo          ⁢                                          ⁢          decoding                                                              Parallel            ⁢                                                  ⁢            encoding                    =                    ⁢                      Encoding            ⁢                                                  ⁢            configuration            ⁢                                                  ⁢            for            ⁢                                                  ⁢            turbo                          ⁢                                  ⁢                                  ⁢                  decoding          ⁢                                          ⁢          which          ⁢                                          ⁢          transmits          ⁢                                          ⁢          the          ⁢                                          ⁢          symbols          ⁢                                          ⁢          using          ⁢                                          ⁢          a                ⁢                                  ⁢                                  ⁢                              parallel            ⁢                                                  ⁢            architecture                    ,                      which            ⁢                                                  ⁢            is            ⁢                                                  ⁢            the            ⁢                                                  ⁢            assumed                          ⁢                                  ⁢                                  ⁢                  architecture          ⁢                                          ⁢          for          ⁢                                          ⁢          this          ⁢                                          ⁢          invention          ⁢                                          ⁢          disclosure                                                  y          ⁡                      (            k            )                          ⁢                                  =                ⁢                  Output          ⁢                                          ⁢          symbols          ⁢                                          ⁢          for          ⁢                                          ⁢                      codeword            /            clock                    ⁢                                          ⁢          k                                                              {                          y              ⁡                              (                                  j                  ⁢                                      <                                    ⁢                  k                                )                                      }                    =                    ⁢                      Output            ⁢                                                  ⁢            symbols            ⁢                                                  ⁢            for            ⁢                                                  ⁢            clocks            ⁢                                                  ⁢            j            ⁢                          =                        ⁢            1                          ,        2        ,        …        ⁢                                  ,                  k          ⁢                      -                    ⁢          1                                                              {                          y              ⁡                              (                                  j                  ⁢                                      >                                    ⁢                  k                                )                                      }                    =                    ⁢                      Output            ⁢                                                  ⁢            symbols            ⁢                                                  ⁢            for            ⁢                                                  ⁢            clocks            ⁢                                                  ⁢            j            ⁢                          =                        ⁢            k            ⁢                          +                        ⁢            1                          ,        ,        2        ,        …        ⁢                                  ,        N             2 Decoding states and observations   3 Current MAP joint probability                               p          ⁡                      (                                          s                ′                            ,              s              ,              y                        )                          =                ⁢                  p          ⁢                                          ⁢                      (                                          s                ′                            ,              s              ,                              y                ⁡                                  (                                      j                    ⁢                                          <                                        ⁢                    k                                    )                                            ,                              y                ⁢                                                                  ⁢                                  (                  k                  )                                            ,                              y                ⁢                                                                  ⁢                                  (                                      j                    ⁢                                          >                                        ⁢                    k                                    )                                                      )                                                                            ⁢                  =                    ⁢                                    β              k                        ⁢                                                  ⁢                          (              s              )                        ⁢                                                  ⁢                                          γ                k                            ⁡                              (                                  s                  ,                                      s                    ′                                                  )                                      ⁢                                                  ⁢                                          α                                  k                  -                  1                                            ⁡                              (                                  s                  ′                                )                                                                                    ⁢                  wherein          ⁢                                          ⁢          by          ⁢                                          ⁢          definition                                                              β            k                    ⁡                      (            s            )                          ⁢                                  =                ⁢                  p          ⁢                                          ⁢                      (                                          y                ⁡                                  (                                      j                    ⁢                                          >                                        ⁢                    k                                    )                                            ❘              s                        )                                                                                      γ              k                        ⁡                          (                              s                ,                                  s                  ′                                            )                                ⁢                                          =                    ⁢                      p            ⁢                                                  ⁢                          (                              s                ,                                                      y                    ⁢                                                                                  ⁢                                          (                      k                      )                                                        ❘                                      s                    ′                                                              )                                      ⁢                                  ⁢                                  ⁢                                            α                              k                -                1                                      ⁡                          (                              s                ′                            )                                =                      p            ⁢                                                  ⁢                          (                                                s                  ′                                ,                                  y                  ⁡                                      (                                          j                      ⁢                                              <                                            ⁢                      k                                        )                                                              )                                           4 New MAP conditional probability                               p          ⁡                      (                          s              ,                                                s                  ′                                ❘                y                                      )                          =                ⁢                  p          ⁢                                          ⁢                      (                          s              ,                                                s                  ′                                ❘                                  y                  ⁡                                      (                                          j                      ⁢                                              <                                            ⁢                      k                                        )                                                              ,                              y                ⁡                                  (                  k                  )                                            ,                              y                ⁡                                  (                                      j                    ⁢                                          >                                        ⁢                    k                                    )                                                      )                                                                            ⁢                  =                    ⁢                                    β              k                        ⁢                                                  ⁢                          (              s              )                        ⁢                                                  ⁢                                          γ                k                            ⁡                              (                                  s                  ❘                                      s                    ′                                                  )                                      ⁢                                                  ⁢                                          α                                  k                  -                  1                                            ⁡                              (                                  s                  ′                                )                                                                                    ⁢                  wherein          ⁢                                          ⁢          by          ⁢                                          ⁢          definition                                                                  ⁢                                            β              k                        ⁡                          (              s              )                                ⁢                                          =                    ⁢                      p            ⁢                                                  ⁢                          (                              s                ❘                                  y                  ⁢                                                                          ⁢                                      (                                          j                      ⁢                                              >                                            ⁢                      k                                        )                                                              )                                                                                        ⁢                                            γ              k                        ⁡                          (                              s                ❘                                  s                  ′                                            )                                ⁢                                          =                    ⁢                      p            ⁢                                                  ⁢                          (                                                s                  ❘                                      s                    ′                                                  ,                                  y                  ⁡                                      (                    k                    )                                                              )                                                                                        ⁢                                            α                              k                -                1                                      ⁡                          (                              s                ′                            )                                ⁢                                          =                    ⁢                      p            ⁡                          (                                                s                  ′                                ❘                                  y                  ⁡                                      (                                          j                      ⁢                                              <                                            ⁢                      k                                        )                                                              )                                          wherein in 2 the decoding states s′,s are defined at clocks k−1,k and the observations are defined over the j=1, 2, . . . , k−1 as y(j<k), over j=k+1, . . . , N as y(j>k), and at k as y(k). In 3 the MAP joint probability p(s′,s,y) expressed as a function of these decoder states and observations is defined as a product of the recursive state estimators α,β and the state transition probability γ. In 4 the new MAP a-posteriori probability p(s,s′|y) is defined as a product of the recursive state estimators α,β and the state transition probability γ using the same notation as in 3 in equations (2) for convenience and wherein p(s,s′|y) reads the probability “p” of “s,s′” conditioned on “y”.
MAP forward recursive equations used to evaluate the state estimator αk(s) is defined in equations (4) in 1a for the current MAP estimator and in 1b for the new MAP estimator, and backward recursive equations used to evaluate the state estimator βk−1(s′) are defined in 2a for the current MAP estimator and in 2b for the new MAP estimator. We find
Forward and backward recursive metric equations(3)1 Forward recursive equation for αk(s)  1a Current MAP    αk(s) = Σall s′ γk(s,s′) αk−1(s′)  1b New MAP    αk(s) = Σall s′ γk(s|s′) αk−1(s′)2 Backward recursive equation for βk−1(s′)  2a Current MAP    βk−1(s′) = Σall s βk(s) γk(s,s′)  2b New MAP    βk−1(s′) = Σall s βk(s) γk(s′ |s)wherein the “Σall s′, Σall s” are the summations over all decoding states “s′,s” defined at clocks “k−1,k” respectively.
MAP transition probabilities γk(s,s′) for the current MAP and γk(s′|s) for the new MAP are defined in 1a,1b respectively in equations (4) assuming zero-mean Gaussian noise for the communications, and the natural logarithms (log) are defined in 2a,2b respectively for application to the forward and backward recursive equations to calculate the state metrics in the logarithm domain for the turbo decoding MAP equations. We find
Natural and log transition probabilities(4)1 Transition probabilities       1    ⁢    a    ⁢                  ⁢    Current    ⁢                  ⁢                  γ        k            ⁡              (                  s          ,                      s            ′                          )                                ⁢                            γ          k                ⁡                  (                      s            ,                          s              ′                                )                    ⁢                          =                                    p            ⁡                          (                              y                ❘                x                            )                                ⁢                                          ⁢                      p            ⁡                          (              x              )                                      ⁢                                  ⁢                                  =                              P            ⁡                          (              X              )                                ⁢                                          ⁢                                    exp              ⁡                              (                                                                            -                                                                                                                              y                            -                            x                                                                                                    2                                                              /                    2                                    ⁢                                      σ                    2                                                  )                                      /                                          (                                  2                  ⁢                                                                          ⁢                  π                                )                                            1                /                2                                              ⁢          σ                          1    ⁢    b    ⁢                  ⁢    New    ⁢                  ⁢                  γ        k            ⁡              (                              s            ′                    ❘          s                )                                ⁢                            γ          k                ⁡                  (                      s            ,                          s              ′                                )                    ⁢                          =                        p          ⁡                      (                          x              ❘              y                        )                          ⁢                                  ⁢                                  =                              p            ⁡                          (              x              )                                ⁢                                          ⁢                                    exp              ⁡                              (                                                                            Re                      ⁡                                              [                                                  yx                          *                                                ]                                                              /                                          σ                      2                                                        -                                                                                                                                        x                                                                          2                                            /                      2                                        ⁢                                          σ                      2                                                                      )                                      /                          {                                                                    (                                          2                      ⁢                                                                                          ⁢                      π                                        )                                                        1                    /                    2                                                  ⁢                σ                            )                                           2 Log transition probabilities simplified       2    ⁢    a    ⁢                  ⁢    Log    ⁢                  ⁢          ln      ⁢                          [                        γ          k                ⁡                  (                      s            ,                          s              ′                                )                    ]        ⁢                  ⁢    simplified                      ⁢                  ln        ⁢                                  [                                            γ              k                        ⁡                          (                              s                ,                                  s                  ′                                            )                                ⁢                                          =                                                                      p                  _                                ⁡                                  (                  x                  )                                            -                                                                                                                                        y                        -                        x                                                                                    2                                    /                  2                                ⁢                σ                                      ⁢                                                  ⁢                                                  =                                                                                p                    _                                    ⁡                                      (                    d                    )                                                  +                                                      DM                    ⁡                                          (                                              s                        ,                                                  s                          ′                                                                    )                                                        ⁢                                                                          ⁢                  2                  ⁢                  b                  ⁢                                                                          ⁢                  Log                  ⁢                                                                          ⁢                                      ln                    ⁢                                                                                  [                                                                  γ                        k                                            ⁡                                              (                                                                              s                            ′                                                    ❘                          s                                                )                                                              ]                                    ⁢                                                                          ⁢                  simplified                  ⁢                                                                          ⁢                                                                          ⁢                                      ln                    ⁢                                                                                  [                                                                  γ                        k                                            ⁡                                              (                                                                              s                            ′                                                    ❘                          s                                                )                                                              ]                                                              =                                                                    p                    _                                    ⁡                                      (                    d                    )                                                  +                                                      Re                    ⁡                                          [                                              yx                        *                                            ]                                                        /                                      σ                    2                                                  -                                                                                                                            x                                                                    2                                        /                    2                                    ⁢                                                                          ⁢                                      σ                    2                                                                                      )            ⁢                          ⁢                          =              DX        ⁢                                  ⁢                  (                      s            ❘                          s              ′                                )                    wherein “DM” is the ML (Maximum Likelihood) decisioning metric for the current turbo and convolutional decoding algorithms defined in 2a, “DX” is the new decisioning metric for the new turbo and convolutional decoding equations defined in 2b, the “y” and “x” are evaluated at index “k”, the probability p(x) is identical to the probability p(d) of the data symbol “d” at index “k” which allows the expression p(d) to be substituted for p(x), the natural logarithm of “p” is represented by “p”, the “2σ2 is the one-sigma noise floor of the Gaussian noise, and the qualifier “simplified” in 3 and 4 means the additive constant terms are deleted since they are cancelled out in the logarithm recursive metric equations.
MAP convolutional decoding forward recursive metric equations (3) and (4) in logarithm format are used to calculate the log(natural logarithm) ln[αk(s)]=αk(s) of αk(s) in 1a, 1b in equations (5) for the current, new MAP, and to calculate backward recursive metric equations for the log ln[βk−1(s′)]=βk1(s′) of βk−1(s′) in 2a,2b for the current, new MAP. We find
MAP logarithm recursive metric equations(5)1 MAP log of forward metric αk(s)  1a Current αk(s)  αk(s) = ln[Σall s′ exp(αk−1(s′)+DM(s|s′)+ p(d(k))]   1b New αk(s)  ak(s) = ln[ Σall s′exp(ak−1(s′)+DX(s|s′))]3 MAP log of backward metric βk−1(s′)  1a Current βk−1(s′)    βk−1(s′)= ln[ Σall s exp ( βk(s)+DM(s|s′)+ p(d(k))]  1b New βk−1(s′)  βk−1(s′)=ln[ Σall s exp (βk(s)+DX(s′|s))]
MAP equations for the log L(d(k)|y) of the likelihood ratio abbreviated to “log likelihood ratio L(d(k)|y)” are derived from equations (1)-(5) for the current MAP and the new MAP. We find
MAP log likelihood ratio L(d(k) | y)(6)1Definition of L(d(k) | y)                                                        L              ⁡                              (                                  d                  ⁡                                      (                    k                    )                                                  )                                      ❘            y                    )                =                ⁢                  ln          ⁢                                          [                      p            ⁡                          (                                                d                  ⁡                                      (                    k                    )                                                  ⁢                                  =                                ⁢                                  +                                ⁢                1                ⁢                                                                          y                    )                                    /                                      p                    (                                                                  d                        ⁡                                                  (                          k                          )                                                                    ⁢                                              =-                                            ⁢                      1                                                                                          ⁢                y                            )                                ]                                        =                ⁢                  ln          ⁢                                          ⁢                      {                                          p                (                                                      d                    ⁡                                          (                      k                      )                                                        ⁢                                      =+                                    ⁢                  1                  ⁢                                                                                  y                      )                                        /                                                  ]                            -                              ln                ⁢                                                                  [                                                      p                    (                                                                  d                        ⁡                                                  (                          k                          )                                                                    ⁢                                              =-                                            ⁢                      1                                                                            ⁢                  y                                )                                      ]                               2Current L(d(k) | y)                                          L            ⁡                          (                                                d                  ⁡                                      (                    k                    )                                                  ❘                y                            )                                =                    ⁢                      ln            ⁢                                                  [                          p              ⁡                              (                                                                            d                      ⁡                                              (                        k                        )                                                              ⁢                                          =+                                        ⁢                    1                                    ,                  y                                )                                      ]                                                                   ⁢                      ln            ⁢                                                  [                          p              ⁡                              (                                                                            d                      ⁡                                              (                        k                        )                                                              ⁢                                          =-                                        ⁢                    1                                    ,                  y                                )                                      ]                                                        =                    ⁢                                    ln              ⁢                                                          [                                                ∑                                      (                                          s                      ,                                                                                                    s                            ′                                                    ❘                                                      d                            ⁡                                                          (                              k                              )                                                                                                      =                                                  +                          1                                                                                      )                                                  ⁢                                  p                  ⁡                                      (                                          s                      ,                                              s                        ′                                            ,                      y                                        )                                                              ]                        ⁢                                                  ⁢                                                  -                          ln              ⁢                                                          [                                                ∑                                      (                                          s                      ,                                                                                                    s                            ′                                                    ❘                                                      d                            ⁡                                                          (                              k                              )                                                                                                      =                                                  -                          1                                                                                      )                                                  ⁢                                  p                  ⁡                                      (                                          s                      ,                                              s                        ′                                            ,                      y                                        )                                                              ]                                            ⁢          ⁢          =            ln      ⁢                          [                        ∑                      (                          s              ,                                                                    s                    ′                                    ❘                                      d                    ⁡                                          (                      k                      )                                                                      =                                  +                  1                                                      )                          ⁢                  exp          ⁢                                          ⁢                      (                                                                                α                    _                                                        k                    -                    1                                                  ⁡                                  (                                      s                    ′                                    )                                            +                              DM                ⁡                                  (                                      s                    ❘                                          s                      ′                                                        )                                            +                                                p                  _                                ⁡                                  (                                      d                    ⁡                                          (                      k                      )                                                        )                                            +                                                                    β                    _                                    k                                ⁡                                  (                  s                  )                                                      )                              ]        ⁢                  ⁢                  -          ln      ⁢                          [                        ∑                      (                          s              ,                                                                    s                    ′                                    ❘                                      d                    ⁡                                          (                      k                      )                                                                      =                                  -                  1                                                      )                          ⁢                  exp          ⁢                                          ⁢                      (                                                                                α                    _                                                        k                    -                    1                                                  ⁡                                  (                                      s                    ′                                    )                                            +                              DM                ⁢                                                                  ⁢                                  (                                      s                    ❘                                          s                      ′                                                        )                                            +                                                p                  _                                ⁡                                  (                                      d                    ⁡                                          (                      k                      )                                                        )                                            +                                                                    β                    _                                    k                                ⁡                                  (                  s                  )                                                      )                              ⁢                          ⁢                           3New L(d(k) | y)]                                                                        L                ⁡                                  (                                      d                    ⁡                                          (                      k                      )                                                        )                                            ❘              y                        )                    =                    ⁢                      ln            ⁢                                                  [                                          ∑                                  (                                      s                    ,                                                                                            s                          ′                                                ❘                                                  d                          ⁡                                                      (                            k                            )                                                                                              =                                              +                        1                                                                              )                                            ⁢                              p                ⁡                                  (                                      s                    ,                                                                  s                        ′                                            ❘                      y                                                        )                                                      ]                                                        -                     ⁢                      ln            ⁢                                                  [                                          ∑                                  (                                      s                    ,                                                                                            s                          ′                                                ❘                                                  d                          ⁡                                                      (                            k                            )                                                                                              =                                              -                        1                                                                              )                                            ⁢                              p                ⁡                                  (                                      s                    ,                                                                  s                        ′                                            ❘                      y                                                        )                                                      ]                                ⁢          ⁢          =            ln      ⁢                          [                        ∑                      (                          s              ,                                                                    s                    ′                                    ❘                                      d                    ⁡                                          (                      k                      )                                                                      =                                  +                  1                                                      )                          ⁢                  exp          ⁢                                          ⁢                      (                                                                                a                    _                                                        k                    -                    1                                                  ⁡                                  (                                      s                    ′                                    )                                            +                              DX                ⁡                                  (                                      s                    ❘                                          s                      ′                                                        )                                            +                                                                    b                    _                                    k                                ⁡                                  (                  s                  )                                                      )                              ]        ⁢                  ⁢                  -          ln      ⁢                          [                        ∑                      (                          s              ,                                                                    s                    ′                                    ❘                                      d                    ⁡                                          (                      k                      )                                                                      =                                  -                  1                                                      )                          ⁢                  exp          ⁢                                          ⁢                      (                                                                                a                    _                                                        k                    -                    1                                                  ⁡                                  (                                      s                    ′                                    )                                            +                              DX                ⁢                                                                  ⁢                                  (                                      s                    ❘                                          s                      ′                                                        )                                            +                                                                    b                    _                                    k                                ⁡                                  (                  s                  )                                                      )                              ]       4Decisioning RulesHard Decisioning: d(k) = +1/−1  when L(d(k) | y) ≧ 0 / < 0Soft decision metric = L(d(k)) | y)wherein the definition in 1 is from references [1],[2], in 2 the first equation uses the Bayes rule P(a,b)=P(alb)P(b) with the p(y) cancelled in the division, in 2 the second equation replaces p(d(k)) with the equivalent sum of the probabilities that the transition from S(k−1)=s′ to S(k)=s occurs for d(k)=+1 and for d(k)=−1, and in 2 the third equation substitutes the equations for the recursive estimators αk(s), βk−1(s′), γk(s,s′). In 3 the first equation replaces p(d(k)) with the equivalent sum of the probabilities that the transition from S(k−1)=s′ to S(k)=s occurs and which are the new probabilities p(s,s′|y) over these transitions, and in 3 the second equation substitutes the equations for the recursive estimators αk(s), βk−1(s′), γk(s|s′). In 4 the hard decisioning rule is d(k)=+/−1 iff L(d(k)|y)≧/<0 and the soft decisioning metric is the value of L(d(k)|y).
MAP turbo decoding iterative algorithm is defined in equations (7) for a parallel architecture using the MAP log likelihood ratio L(d(k)|y) in equations (6) for decoding of the encoded data bit stream estimated by QLM demodulation. This basic algorithm is used to illustrate how the decisioning metrics DM,DX are implemented, and is representative of how the DM,DX metrics are used for the more efficient algorithms such as the Log-MAP, Max-Log-MAP, iterative SOVA, and others, for parallel and serial architectures and other variations.
A representative MAP decoder parallel architecture is depicted in FIG. 3. Inputs are the detected soft output symbols 8 from the QLM demodulator which detects and recovers these symbols. This stream of output symbols consists of the outputs {y(k,b=1)} for the systematic bit b=1 which is the uncoded bit, the subset of the output symbols from #1 encoder 3 in FIG. 1, and the remaining output symbols from #2 encoder 5 in FIG. 1. Systematic bits are routed to both #1 decoder 12 and #2 decoder 15. Encoded bits from #1 and #2 encoders are separately routed 9 to #1 and #2 decoders. In equations (7), step 1 defines the various parameters used in the turbo decoding iterations.
Step 2 starts iteration i=1 in FIG. 3 for #1 decoder 12. Extrinsic information L1e from this decoder 12 in FIG. 3 for i=1 is calculated in step 2 in equations (7) using the soft outputs {y(k,b=1)} 10 of the received channel for the systematic bit b=1 which is the uncoded bit, the subset of the detected output symbols 9 which are from #1 decoder 3 in FIG. 1, and the #1 decoder likelihood ratio output L1 calculated in 2,3 in equations (6). The a-priori information on p(d(k)) in 2,3 in equations (6) from #2 decoder 15 is not available which means p(d(k))=0 corresponding to p(d(k)=+1)=p(d(k)=−1)=½.
MAP turbo decoding iterative algorithm(7)Step 1 Definitions                                                                                          L                  m                                =                                ⁢                                  {                                      L                    ⁡                                          (                                                                        d                          ⁡                                                      (                            k                            )                                                                          ❘                        y                                            )                                                        )                                            ,                                                          ⁢                              k                ⁢                                  =                                ⁢                1                            ,              2              ,                              …                ⁢                                                                  .                                      }                    ⁢                                          ⁢          for          ⁢                                          ⁢          m          ⁢                      =                    ⁢          #1                ,                  #2          ⁢                                          ⁢          decoders                                        =                ⁢                  a          ⁢                      -                    ⁢          posteriori          ⁢                                          ⁢          likelihood          ⁢                                          ⁢          ratio                                                                            L              me                        =                        ⁢                          {                                                L                  me                                ⁡                                  (                                                            d                      ⁡                                              (                        k                        )                                                              ❘                    y                                    )                                            )                                ,                                          ⁢                      k            ⁢                          =                        ⁢            1                    ,          2          ,                      …            ⁢                                                  .                          }                                          =                    ⁢                      extrinsic            ⁢                                                  ⁢            information            ⁢                                                  ⁢            from            ⁢                                                  ⁢            m            ⁢                          =                        ⁢            #1                          ,                  #2          ⁢                                          ⁢          decoder                                                  =                    ⁢                      a            ⁢                          -                        ⁢            priori            ⁢                                                  ⁢            estimates            ⁢                                                  ⁢            of            ⁢                                                  ⁢                          ln              ⁡                              [                                                      p                    ⁡                                          (                                              d                        ⁢                                                  =+                                                ⁢                        1                                            )                                                        /                                      p                    ⁡                                          (                                              d                        ⁢                                                  =-                                                ⁢                        1                                            )                                                                      ]                                                    ⁢                                  ⁢                                  ⁢                  which          ⁢                                          ⁢          defines          ⁢                                          ⁢                      p            _                    ⁢                                          ⁢          for          ⁢                                          ⁢          the          ⁢                                          ⁢          other          ⁢                                          ⁢          decoder          ⁢                                          ⁢          using                ⁢                                  ⁢                                  ⁢                  equations          ⁢                                          ⁢                      (            8            )                    ⁢                                          ⁢          to          ⁢                                          ⁢          solve          ⁢                                          ⁢          for          ⁢                                          ⁢                      p            _                                                                                      L              ~                                      1              ⁢              e                                =                    ⁢                      Interleaved            ⁢                                                  ⁢                          L                              1                ⁢                e                                                    ⁢                                  ⁢                                            L              ~                                      2              ⁢              e                                ,                                                    L                ~                            2                        ⁢                                                  =                          De              ⁢                              -                            ⁢              interleaved              ⁢                                                          ⁢                              L                                  2                  ⁢                  e                                                              ,                      L            2                          ⁢                                  ⁢                              y            ⁡                          (                              k                ,                                  b                  ⁢                                      =                                    ⁢                  1                                            )                                =                      y            ⁢                                                  ⁢            for            ⁢                                                  ⁢            uncoded            ⁢                                                  ⁢            bit            ⁢                                                  ⁢            b            ⁢                          =                        ⁢            1                          ⁢                                  ⁢                                  ⁢                                            y              ~                        ⁡                          (                              k                ,                                  b                  ⁢                                      =                                    ⁢                  1                                            )                                =                      interleaved            ⁢                                                  ⁢            y            ⁢                                                  ⁢            for            ⁢                                                  ⁢            uncoded            ⁢                                                  ⁢            bit            ⁢                                                  ⁢            b            ⁢                          =                        ⁢            1                               Step 2 Iteration i=1 starts the turbo decodingL1e = L1 − 0 − (2/σ2) Re[y(k, b=1)]L2e = L2 − {tilde over (L)}1e − (2/σ2) Re[{tilde over (y)} (k, b=1)]where Re(o) = Real(o)Step 3 For iteration i=2, 3, . . . L1e = L1 − {tilde over (L)}2e − (2/σ2) Re[y(k, b=1)]L2e = L2 − {tilde over (L)}1e − (2/σ2) Re[{tilde over (y)} (k, b=1)}Step 4 Decode after last iterationDecide {circumflex over (d)}(k) =+1/−1 ≡ 1/0 bit valuefor {tilde over (L)}2 (d(k)|y)≧/>0 for k=1,2, . . . where {circumflex over (d)}(k) is the estimate of d(k) from turbodecoding
Step 2 next proceeds to #2 decoder 15. A-priori estimates for p(d(k)) are calculated from the extrinsic information from #1 decoder after interleaving 13 in FIG. 3 in order to align the bits with the interleaved bits 4 in FIG. 1 which are encoded by the #2 encoder 5. Calculation of the a-priori p for #1,#2 decoder using the extrinsic information from #2,#1 decoder is given in equations (8) from references [2], [4].
A-priori calculation of p in 2,3 in equations (6)
                              A          ⁢                      -                    ⁢          priori          ⁢                                          ⁢          calculation          ⁢                                          ⁢          of          ⁢                                          ⁢                      p            _                    ⁢                                          ⁢          in          ⁢                                          ⁢          2                ,                  3          ⁢                                          ⁢          in          ⁢                                          ⁢          equations          ⁢                                          ⁢                      (            6            )                                              (        8        )                                          K          =                    ⁢                      [                          1              +                              exp                ⁡                                  (                                                            L                      ~                                        me                                    )                                                      ]                          ⁢                                  ⁢                                            p              _                        ⁡                          (                                                d                  ⁡                                      (                    k                    )                                                  =                                  -                  1                                            )                                =                    ⁢                      -                          ln              ⁡                              (                K                )                                                    ⁢                                  ⁢                                            p              _                        ⁡                          (                                                d                  ⁡                                      (                    k                    )                                                  =                                  +                  1                                            )                                =                    ⁢                                                    L                ~                            me                        -                          ln              ⁡                              (                K                )                                                                                    Inputs to the #2 decoder 15 in FIG. 3 are the detected output symbols 9 from the #2 encoder 5 in FIG. 1, the detected symbols for the systematic bits 11 after interleaving 14, and the extrinsic information from #1 decoder 12 after interleaving 13. Calculation of the extrinsic information L2e from #2 decoder is given in step 2 in equations (7).
Step 3 repeats step 2 with the subtraction of the de-interleaved 16 extrinsic information input {tilde over (L)}2e to #1 decoder 12 from #2 decoder 15. This {tilde over (L)}2e is used to calculate the a-priori probabilities p using equations (8) for use in the evaluation of the a-posterior likelihood ratio L1 from decoder #1, and also used in the calculation of the extrinsic information L1e for decoder #1 in step 3 in equations (7).
Step 4 is the calculation of the estimates { d(k)} for the transmitted information {d(k)} in the form of +/−1 used in the iterative algorithm to model the BPSK modulation with values +/−1 for the estimated input signal {{circumflex over (d)}(k)} in 18 with +1 corresponding to the bit value 1 and −1 for the bit value 0. The de-interleaved 17 a-posteriori maximum likelihood ratio {tilde over (L)}2 from #2 decoder in FIG. 3 yields these output bits 18 using the hard decisioning rule that decides 1/0 depending on whether the {tilde over (L)}2 is ≧0 or <0.
Convolutional decoding solves the recursive equations derived from equations (5) by replacing the summations over all possible transitions with the best transition path to each of the new trellis states. The best transition path for convolutional decoding is the best choice of s′ for each forward path s′→s and the best choice of s for each backward path s→s′, where best is the maximum value of the state metric for the path transitions.
For the forward and backward recursion log ML equations are derived in equations (9) using the redefined state path metrics αk(s), βk−1(s′) and the state transition decisioning function DM. We find
Forward equations for ML convolutional decoding(9)1The ML probability density has the well-knownfactorization assuming a memoryless channel      p    ⁡          (                        y          ⁡                      (            k            )                          ❘        s            )        =                    Π                              j            =            1                    ,          …          ,                      k            -            1                              ⁢              p        ⁡                  (                                    y              ⁡                              (                j                )                                      ❘                                          s                                  j                  -                  1                                            ->                              s                j                                              )                      ⁢                  ⁢                  =                  p        ⁡                  (                                    y              ⁡                              (                k                )                                      ❘                                          s                ′                            ->              s                                )                    ⁢                          ⁢              p        ⁡                  (                                    y              ⁡                              (                                  k                  -                  1                                )                                      ❘                          s              ′                                )                    2State path metric αk(s) in log format isαk(s) = p(y(k) | s)3Forward equations for αk(s) are derived using 2and the log of 1 to yield                                                        α              _                        k                    ⁡                      (            s            )                          ⁢                                  =                                            max                              s                ′                                      ⁢                                                  ⁢                          [                                                                    p                    _                                    ⁡                                      (                                                                  y                        (                                                  k                          ⁢                                                      -                                                    ⁢                          1                                                )                                            ❘                                              s                        ′                                                              )                                                  +                                                      p                    _                                    ⁡                                      (                                                                  y                        ⁡                                                  (                          k                          )                                                                    ❘                                                                        s                          ′                                                ->                        s                                                              )                                                              ]                                ⁢                                          ⁢                                          =                                          ⁢                                    max                              s                ′                                      ⁢                                                  ⁢                          [                                                                                          α                      _                                        k                                    ⁡                                      (                    s                    )                                                  +                                  DM                  ⁡                                      (                                          s                      ❘                                              s                        ′                                                              )                                                              ]                                          ⁢                          ⁢                        DM          ⁡                      (                          s              ❘                              s                ′                                      )                          =                              p            _                    ⁡                      (                                          y                ⁡                                  (                  k                  )                                            ❘                                                s                  ′                                ->                s                                      )                                ]    ⁢          ⁢          =                    -                                                                        y                ⁡                                  (                  k                  )                                            -                              x                ⁡                                  (                  k                  )                                                                          2                    /      2        ⁢                  ⁢          σ      2      4Backward equations for βk−1(s′) are derived                              β          _                          k          -          1                    ⁡              (                  s          ′                )              =                            max          s                ⁢                                  ⁢                  [                                    p              _                        ⁡                          (                                                                    y                    ⁡                                          (                                              j                        ⁢                                                  >                                                ⁢                        k                                            )                                                        ⁢                                                          s                    )                                                  +                                                                            p                      _                                        (                                          s                      ,                                              y                        ⁡                                                  (                          k                          )                                                                                                                          ⁢                                      s                    ′                                                              )                                ]                    ⁢                          ⁢                          =                        max          s                ⁢                                  ⁢                  [                                                                      β                  _                                k                            ⁡                              (                s                )                                      +                          DM              ⁡                              (                                  s                  ❘                                      s                    ′                                                  )                                              ]                          using    ⁢                  ⁢    the    ⁢                  ⁢    definition                      ⁢                                        β            _                                k            -            1                          ⁡                  (                      s            ′                    )                    =                        ln          ⁡                      [                          p              ⁡                              (                                                      y                    ⁡                                          (                                              j                        ⁢                                                  >                                                ⁢                        k                        ⁢                                                  -                                                ⁢                        1                                            )                                                        ,                                      s                    ′                                                  )                                      ]                          ⁢                                  ⁢                                  =                  p          (                      y            ⁡                          (                                                j                  ⁢                                      >                                    ⁢                  k                  ⁢                                      -                                    ⁢                  1                                ❘                                  s                  ′                                            )                                ]                    
In step 1 the factorization of the ML probability is allowed by the memoryless channel assumption. Step 2 is the definition of the path metric αk(s) in log format which is different from its definition in 1 in equations (4) for MAP turbo decoding. Step 3 derives the forward recursive equation for αk(s) by combining the equations in 1 and 2 and using the definition of the ML decisioning metric DM=ln[p(y(k)|s′→s)]=p(y(k)|s′→s)] for the path s′→s for convolutional decoding. Path metrics and the corresponding data d(k) bit for each trellis state are stored in a state matrix. The best path corresponding to decoding state k is used to select the best data d(k−D) bit decision at the state k−D of this path stored in the state matrix, where D is a delay in the data bit decisioning that is required for reliable decoding. In 4 the backward recursion log ML equation is derived following a similar logic starting with the definition for βk−1(s′).
Convolutional decoding forward recursive metric equations for calculation of the logarithm ln[αk(s)]=αk(s) of αk(s) are derived in 1,2,3 in equations (10) for the current ML, current MAP, and the new MAP,
Convolutional decoding forward equations(10)1 Current ML decisioning metric                    α        _            k        ⁡          (      s      )        =            max              s        ′              ⁢                  ⁢          [                                                  α              _                                      k              -              1                                ⁡                      (                          s              ′                        )                          +                  DM          ⁡                      (                          s              ❘                              s                ′                                      )                              ]      2 Current MAP decisioning metric                    α        _            k        ⁡          (      s      )        =            max              s        ′              ⁢                  ⁢          [                                                  α              _                                      k              -              1                                ⁡                      (                          s              ′                        )                          +                  DM          ⁡                      (                          s              ❘                              s                ′                                      )                          +                  p          ⁡                      (            d            )                              ]      3 New MAP decisioning metric                    α        _            k        ⁡          (      s      )        =            max              s        ′              ⁢                  ⁢          [                                                  α              _                                      k              -              1                                ⁡                      (                          s              ′                        )                          +                  DX          ⁡                      (                          s              ❘                              s                ′                                      )                              ]      and in 1,2,3 in equations (11) for the backward recursive metric equations for calculation of the logarithm ln[βk−1(s′)]=βk−1(s′) of βk−1(s′) for the current ML, current MAP, and the new MAP. We find
Convolutional decoding backward equations(11)1 Current ML decisioning metric                    β        _                    k        -        1              ⁡          (              s        ′            )        =            max      s        ⁢                  ⁢          [                                                  β              _                        k                    ⁡                      (            s            )                          +                  DM          ⁡                      (                          s              ❘                              s                ′                                      )                              ]      2 Current MAP decisioning metric                    β        _                    k        -        1              ⁡          (              s        ′            )        =            max      s        ⁢                  ⁢          [                                                  β              _                        k                    ⁡                      (            s            )                          +                  DM          ⁡                      (                          s              ❘                              s                ′                                      )                          +                  p          ⁡                      (            d            )                              ]      3 New MAP decisioning metric                    β        _                    k        -        1              ⁡          (              s        ′            )        =            max      s        ⁢                  ⁢          [                                                  β              _                        k                    ⁡                      (            s            )                          +                  DX          ⁡                      (                          s              ❘                              s                ′                                      )                              ]      wherein it should be noted that the new log MAP equations are the correct formulation from a probabilistic theorectic viewpoint and offer promise for improved decisioning metric performance as demonstrated in U.S. Pat. No. 7,337,383 B1.